package algorithm.leetcode.I201to400;


/**
 * 暴力穷举会超时,测试用例是[1,2,4], 32, 答案是39882198
 * 用dp
 *
 * 本题和518不一样的地方在于前者是求排列数,后者是组合数
 *
 * 背包的组合问题: 377, 494, 518
 * 背包true false问题: 139, 416
 * 背包最大最小问题: 474, 322
 *
 * https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92.md#0-1-%E8%83%8C%E5%8C%85
 *
 */


//   0 1 2 3 4 5  6
// 1 1 1 1 1 1 1  1
// 2 1 1 2 3 5 8  13
// 4 1 1 2 3 6 10 18
//
// 其中18=10+6+2
//
// 为什么这个计算出来的就是排列数?
// 如上表横行2,纵列3的格子数字3,是由1+2而来
// 1表示(1,2)两个硬币凑成1块的排列数,只有1,再凑成3是1+2
// 2表示(1,2)两个硬币凑成2块的排列数,有1+1和2,再凑成3是1+1+1和2+1
//
// 而如果是求组合数的话
// 应该是横行1纵列3的1加上横行2纵列3-2=1的格子里的1=2
// 横行1纵列3的1表示仅由1组成3块的数量为1种(即1+1+1)
// 横行2纵列3-2=1表示由1和2组成1块的数量为1种(即1)



public class Q377 {

    public int combinationSum4(int[] nums, int target) {
        // 初始化dp数组
        int[] dp = new int[target + 1];
        for (int num : nums) {
            if (num <= target) dp[num] = 1;
        }

        // 递推dp数组
        for (int i = 0; i < dp.length; i++) {
            // 循环每个数字
            for (int num : nums) {
                if (i - num >= 0) dp[i] += dp[i-num];
            }
        }
        return dp[target];
    }


    public static void main(String[] args) {
        Q377 q377 = new Q377();
        System.out.println(q377.combinationSum4(new int[]{1}, 6));
    }
}
